package com.leo.basic.chapter06.unionFindSet;

/**
 * 可以改进的方向：维护每个节点的下面层数，union的时候，将个数少的节点连接到个数多的节点上面
 * @author xuexiaolei
 * @version 2017年12月13日
 */
public class UFS05 {
    private int[] mParents;
    //mRank[i]表示以i为根节点的集合所表示的树的层数
    private int[] mRank;
    private int mCount;
    public UFS05(int capacity){
        mCount = capacity;
        mParents = new int[mCount];
        mRank = new int[mCount];
        for (int i = 0; i < mCount; i++) {
            mParents[i] = i;
            //默认每个都是1：表示深度为1层
            mRank[i] = 1;
        }
    }
    //以下find和isConnected都用不到mRank.
    public int find(int p){
        if( p<0 || p>=mCount){
            //...做一些异常处理
        }
        while(p!=mParents[p]){
            p = mParents[p];
        }
        return p;
    }
    public boolean isConnected(int p,int q){
        return find(p)==find(q);
    }
    //找到p、q节点所在的树形集合的根节点，它的深度。然后把深度小的根节点合入到深度大的根节点当中
    public void union(int p,int q){
        //前两步不变
        int pRoot= find(p);
        int qRoot = find(q);
        if(pRoot == qRoot){
            return;
        }
        int pRank = mRank[pRoot];//初始事都是深度为1
        int qRank= mRank[qRoot];
        //如果p的深度比q的深度大.
        if(pRank > qRank){
            //注意是小的指向大的,也就是为小的重新读之
            mParents[qRoot] = pRoot;
            //此时把并不需要维护pRank,因为qRank是比pRank小的
            //也就是q更浅，它不会增加p的深度，只会增加去p的宽度
        }else if(pRank < qRank){
            mParents[pRoot] = qRoot;
            //同样的道理不需要维护qRank,p只会增加它的宽度
        }else{
            //当两个深度相同的时候,谁指向谁都可以，但是注意此时的深度维护
            //被指向的那个的深度需要加1.
            //此时让qRoot指向pRoot吧.
            mParents[qRoot] = pRoot;
            mRank[pRoot]++;
        }
    }
}
